首页 > 试题广场 >

设计LFU缓存结构

[编程题]设计LFU缓存结构

热度指数：23499 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个缓存结构需要实现如下功能。

set(key, value)：将记录(key, value)插入该结构
get(key)：返回key对应的value值

但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；

如果调用次数最少的key有多个，上次调用发生最早的key被删除

这就是LFU缓存替换算法。实现这个结构，K作为参数给出

数据范围： $0 < k \le 10^5$ ， $|val| \le 2 \times 10^9$

要求：get和set的时间复杂度都是 $O(logn)$ ，空间复杂度是 $O(n)$

若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1

对于每个操作2，返回一个答案

示例1

输入

[[1,1,1],[1,2,2],[1,3,2],[1,2,4],[1,3,5],[2,2],[1,4,4],[2,1]],3

输出

[4,-1]

说明

在执行"1 4 4"后，"1 1 1"被删除。因此第二次询问的答案为-1

备注:

算法知识视频讲解

Python 3

今天该收到offer了吧

# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

# lfu design

# @param operators int整型二维数组 ops

# @param k int整型 the k

# @return int整型一维数组

class Solution:

def LFU(self, operators: List[List[int]], k: int) -> List[int]:

# write code here

dic_val = {}

dic_num = {} #当前值的访问次数，和访问顺序 key->int: value->[次数，顺序]

res = []

for i, ope in enumerate(operators):

if ope[0] == 1:

if len(dic_val) == k:

if ope[1] not in dic_val.keys():

key = sorted(dic_num.items(), key=lambda x: (x[1][0], x[1][1]))

dic_num.pop(key[0][0])

dic_val.pop(key[0][0])

dic_val[ope[1]] = ope[2]

if ope[1] in dic_num.keys():

dic_num[ope[1]] = [dic_num[ope[1]][0] + 1, i]

else:

dic_num[ope[1]] = [1, i]

else:

if ope[1] in dic_val.keys():

res.append(dic_val[ope[1]] )

if ope[1] in dic_num.keys():

dic_num[ope[1]] = [dic_num[ope[1]][0] + 1, i]

else:

dic_num[ope[1]] = [1, i]

else:

res.append(-1)

return res

发表于 2023-10-07 15:25:34 回复(0)

Python 3

taxueguilai

class Solution:
    def __init__(self) -> None:
        self.dic = {}

    def get_key(self):
        # 根据操作个数和tp的值对key进行排序，得到最不常用的key
        key = sorted(self.dic.items(), key=lambda x: (x[1][1], x[1][2]))[0][0]
        return key

    def get(self, key, tp):
        val = self.dic.get(key, None)
        if val != None:
            self.dic[key][1] += 1
            self.dic[key][2] = tp
            return val[0]
        else:
            return -1

    # 巧妙的使用 tp 来解决个数相等时的先后问题
    def set(self, key, val, tp):
        if key in self.dic.keys():
            self.dic[key][0] = val
            self.dic[key][1] += 1
            self.dic[key][2] = tp
        else:
            if len(self.dic.keys()) == self.size:
                self.dic.pop(self.get_key())
            self.dic[key] = [val, 1, tp]

    def LFU(self, operators: List[List[int]], k: int) -> List[int]:
        # write code here
        result = []
        self.size = k
        for i in range(len(operators)):
            if operators[i][0] == 1:
                self.set(operators[i][1], operators[i][2], i)
            else:
                res = self.get(operators[i][1], i)
                result.append(res)
        return result

发表于 2023-07-19 23:32:38 回复(0)

Python 3

收心碎的找工作er

    def LFU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here
        result = []
        record = []
        recordkv = dict()
        recordnum = 0
        flag = 0
        if operators == None:
            return result
        for op in operators:   
            if op[0] == 1:
                if flag >= k :
                   del recordkv[record[0]]
                   record.pop(0) 
                   flag -= 1
                recordkv[op[1]] = op[2]
                if op[1] in record:
                    record.remove(op[1])
                record.append(op[1])
                flag += 1
                
            if op[0] == 2:
                if op[1] not in record:
                    result.append(-1)
                else:
                    result.append(recordkv[op[1]])
                    record.remove(op[1])
                    record.append(op[1])
                    #print(record)
        return resul

有一个用例不过，最后一个用例？帮忙看下大神

发表于 2023-05-26 18:14:21 回复(0)

Python 3

英俊的嘟教授上岸了

from typing import List


class Solution:
    def LFU(self , operators: List[List[int]], k: int) -> List[int]:
        one_dict = {}
        two_dict = {}
        res = []
        if not operators:
            return res
        for three_int in operators:
            if three_int[0] == 1:
                self.set(three_int[1], three_int[2], k, one_dict, two_dict)
            else:
                res_t = self.get((three_int[1]), one_dict, two_dict, res)
        return res
    def set(self, key:int, value:int, k:int, dict_one, dict_two):
        # 已满
        if len(dict_one) == k:
            # 已存在，不需要删除
            if key in dict_one.keys():
                next_key = dict_one[key]
                for key_val in dict_two[next_key]:
                    if key_val[0] == key:
                        object = [key, key_val[1]]
                        dict_two[next_key].remove(object)
                        if not dict_two[next_key]:
                            dict_two.pop(next_key)
                        object = [key, value]
                        dict_one[key] += 1
                        if next_key+1 in dict_two.keys():
                            dict_two[next_key+1].append(object)
                        else:
                            dict_two[next_key+1] = [object]
                        break
            # 不存在，需要删除
            else:
                # 先找到当前要删除的key value
                for i in range(1, len(dict_one)):
                    if i in dict_two.keys():
                        pop_node = dict_two[i].pop(0)
                        pop_key = pop_node[0]
                        dict_one.pop(pop_key)
                        break
                dict_one[key] = 1
                if 1 in dict_two.keys():
                    dict_two[1].append([key, value])
                else:
                    dict_two[1] = [[key, value]]
        # 未满
        else:
            # 已存在
            if key in dict_one.keys():
                next_key = dict_one[key]
                for key_val in dict_two[next_key]:
                    if key_val[0] == key:
                        object = [key, key_val[1]]
                        dict_two[next_key].remove(object)
                        if not dict_two[next_key]:
                            dict_two.pop(next_key)
                        object = [key, value]
                        dict_one[key] += 1
                        if next_key + 1 in dict_two.keys():
                            dict_two[next_key + 1].append(object)
                        else:
                            dict_two[next_key + 1] = [object]
                        break
            # 不存在
            else:
                dict_one[key] = 1
                if 1 in dict_two.keys():
                    dict_two[1].append([key, value])
                else:
                    dict_two[1] = [[key, value]]

    def get(self, key:int, dict_one, dict_two ,res) -> int:
        if key in dict_one.keys():
            next_key = dict_one[key]
            for key_val in dict_two[next_key]:
                if key_val[0] == key:
                    val = key_val[1]
                    object = [key, val]
                    dict_two[next_key].remove(object)
                    if not dict_two[next_key]:
                        dict_two.pop(next_key)
                    dict_one[key] += 1
                    if next_key + 1 in dict_two.keys():
                        dict_two[next_key + 1].append(object)
                    else:
                        dict_two[next_key + 1] = [object]
                    res.append(val)
                    break
        else:
            res.append(-1)

发表于 2022-08-06 11:10:48 回复(0)

Python 3

东方佑

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组
#
class Solution:
    def LFU(self , operators: List[List[int]], k: int) -> List[int]:
        # write code here

        self.capacity=k
        self.capacity_data=dict()
        self.key_list=[]
        get_res=[]
        for i in operators:
            if len(i)>=3:
                self.set(i[1],i[2])
            else:
                val=self.get(i[1])
#                 print(i[1])
                get_res.append(val)
        return get_res


    def get(self, key: int) -> int:
        # write code here
        if key in self.key_list:

            self.key_list.remove(key)
            self.key_list.insert(0,key)
            return self.capacity_data.get(key)
        else:
            return -1

    def set(self, key: int, value: int) :

        # write code here
#         print(len(self.capacity_data.keys()))
        if key not in self.key_list:
            if len(self.key_list)>=self.capacity:
                self.capacity_data.pop(self.key_list.pop())
                self.key_list.insert(0,key)
                self.capacity_data[key]=value
            else:
                self.key_list.insert(0,key)
                self.capacity_data[key]=value

        else:
            self.key_list.remove(key)
            self.key_list.insert(0,key)
            self.capacity_data[key]=value

请问这有什么bug

发表于 2022-06-08 11:47:00 回复(0)

Python 3

牛客537198052号

#
# lfu design
# @param operators int整型二维数组 ops
# @param k int整型 the k
# @return int整型一维数组

class Solution:
def LFU(self, operators, k) :
# write code here
self.dic = dict()
self.dic_freq = dict()
self.list_freq = dict()
self.min = 0
self.k = k
self.listreturn = []
for operator in operators:
if operator[0] == 1:
self.set(operator[1], operator[2])
elif operator[0] == 2:
self.listreturn.append(self.get(operator[1]))
return self.listreturn

def set(self, key, value):
if key in self.dic:
freq = self.list_freq[key]
self.dic[key] = value
self.list_freq[key] = freq + 1
self.dic_freq[freq].pop(self.dic_freq[freq].index(key))
if freq+1 in self.dic_freq:
self.dic_freq[freq+1].append(key)
else:
self.dic_freq[freq + 1] = []
self.dic_freq[freq+1].append(key)
if not self.dic_freq[freq]:
self.min += 1

else:
if len(self.dic) < self.k:
self.dic[key] = value
self.min = 1
self.list_freq[key] = 1
if self.min in self.dic_freq:
self.dic_freq[self.min].append(key)
else:
self.dic_freq[self.min] = []
self.dic_freq[self.min].append(key)
else:
rm = self.dic_freq[self.min].pop(0)
self.list_freq.pop(rm)
self.dic.pop(rm)
self.dic[key] = value
self.list_freq[key] = 1
if len(self.dic_freq[self.min]) == 0:
self.dic_freq.pop(self.min)
self.min = 1
if self.min in self.dic_freq:
self.dic_freq[self.min].append(key)
else:
self.dic_freq[self.min] = []
self.dic_freq[self.min].append(key)

def get(self, key):
if key in self.dic:
freq = self.list_freq[key]
self.list_freq[key] = freq + 1
self.dic_freq[freq].pop(self.dic_freq[freq].index(key))
if len(self.dic_freq[freq]) == 0:
self.dic_freq.pop(freq)
if freq+1 in self.dic_freq:
self.dic_freq[freq+1].append(key)
else:
self.dic_freq[freq+1] = []
self.dic_freq[freq+1].append(key)
if self.min not in list(self.dic_freq.keys()):
self.min +=1
value = self.dic[key]
return value
else:
return -1

发表于 2022-04-10 09:21:45 回复(0)

Python 3

给个offer～

有序字典居然可以通过，只是尝试了一下。

def LFU(self , operators , k ):
        # write code here
        dic = collections.OrderedDict()
        ret = []
        for op in operators:
            if op[0] == 1:
                if len(dic) == k and op[1] not in dic:
                    keys = list(dic.keys())
                    min_key = keys[0]
                    for i in range(1,len(keys)):
                        if dic[keys[i]][1] < dic[min_key][1]:
                            min_key = keys[i]
                    dic.pop(min_key)
                if op[1] in dic:
                    dic[op[1]][0] = op[2]
                    dic[op[1]][1] += 1
                    value = dic[op[1]]
                    dic.pop(op[1])
                    dic[op[1]] = value
                else:
                    dic[op[1]] = [op[2],1]

            else:
                if op[1] not in dic:
                    ret.append(-1)
                else:
                    ret.append(dic[op[1]][0])
                    dic[op[1]][1] += 1
                    val = dic[op[1]]
                    dic.pop(op[1])
                    dic[op[1]] = val
        return ret

发表于 2021-08-10 17:29:21 回复(0)